import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-12-18
 * Time: 15:14
 */
public class Test {
    /**
     * 1.长度最小的子数组-找出该数组中满足其总和大于等于 target 的长度最小的子数组
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        int sum = 0;
        int n = nums.length;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];//进窗口
            while (sum >= target) {//判断
                len = Math.min(len, right - left + 1);//更新结果
                sum -= nums[left++];//出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    /**
     * 2.无重复字符的最长子串
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        char[] ch = s.toCharArray();
        int len = 0;
        int[] hash = new int[128];//用数字模拟哈希表
        for(int left = 0, right = 0; right < ch.length; right++) {
            hash[ch[right]]++;//进窗口
            while(hash[ch[right]] > 1) {//判断
                hash[ch[left++]]--;//出窗口
            }
            len = Math.max(len,right-left+1);//修改结果
        }
        return len;
    }
    public static int lengthOfLongestSubstring2(String s) {
        int len = 0;
        char[] ch = s.toCharArray();
        HashSet<Character> hash = new HashSet<>();
        for(int left = 0, right = 0; right < ch.length; right++) {
            while(left < right && hash.contains(ch[right])) {
                hash.remove(ch[left++]);
            }
            hash.add(s.charAt(right));
            len = Math.max(len,right-left+1);
        }
        return len;
    }

    /**
     * 3.最大连续1的个数 III
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums
     * @param k
     * @return
     */
    public static int longestOnes(int[] nums, int k) {
        int len = 0;
        for(int left = 0, right = 0,zero = 0; right < nums.length; right++) {
            if(nums[right] == 0) zero++;//进窗口
            while(zero > k )
                if(nums[left++] == 0) zero--;//出窗口
            len = Math.max(len,right-left+1);//更新结果
        }
        return len;
    }


    /**
     * 4.将 x 减到 0 的最小操作数
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums
     * @param x
     * @return
     */
    public static int minOperations(int[] nums, int x) {
        int n = nums.length, len = -1, all = 0;
        for(int num : nums) all += num;
        //正难则反
        //求出最长的数组，使其所在区间的值等于整个数组的和-x
        int target = all - x;
        //处理细节
        if(target < 0) return -1;//因为所有的数都为正整数，不可能找到一个和为负数的区间
        for(int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += nums[right];//进窗口
            while(sum > target) {
                sum -= nums[left++];//出窗口
            }
            if(sum == target) len = Math.max(len,right-left+1);//更新结果
        }
        return len == -1 ? len : n - len;
    }

    /**
     *5.水果成篮
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param fruits
     * @return
     */
    public static int totalFruit(int[] fruits) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        int len = 0;
        for(int left = 0, right = 0; right < fruits.length; right++) {
            int in = fruits[right];
            hash.put(in,hash.getOrDefault(in,0)+1);//进窗口
            while(hash.size() > 2) {
                int out = fruits[left];
                hash.put(out,hash.get(out)-1);//出窗口
                if(hash.get(out) == 0) hash.remove(out);
                left++;
            }
            len = Math.max(len,right-left+1);//更新结果
        }
        return len;
    }

    public static int totalFruit2(int[] fruits) {
        int n = fruits.length;
        //用数组的下标表示种类，用数组的值表示个数
        int[] hash = new int[n + 1];
        int len = 0;
        for(int left = 0, right = 0, kinds = 0; right < n; right++) {
            int in = fruits[right];
            if(hash[in] == 0) kinds++;
            hash[in]++;//进窗口
            while(kinds > 2) {
                int out = fruits[left];
                hash[out]--;//出窗口
                if(hash[out] == 0) kinds--;
                left++;
            }
            len = Math.max(len,right-left+1);//更新结果
        }
        return len;
    }

    /**
     * 6.找到字符串中所有字母异位词
     * 异位词：字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param ss
     * @param pp
     * @return
     */
    public static List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list = new ArrayList<>();
        char[] p = pp.toCharArray();
        char[] s = ss.toCharArray();

        int[] hash1 = new int[26];
        for(char ch : p) hash1[ch - 'a']++;

        int[] hash2 = new int[26];
        int m = p.length;
        for(int left = 0, right = 0, count = 0; right < s.length;right++) {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) {//进窗口
                count++;//维护count
            }
            if(right - left + 1 > m) {
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) {//出窗口
                    count--;//维护count
                }
            }
            //更新结果
            if(count == m) list.add(left);
        }
        return list;
    }

    /**
     * 7.串联所有单词的子串
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String,Integer> hash1 = new HashMap<>();
        for(String word : words) hash1.put(word,hash1.getOrDefault(word,0)+1);
        int len = words[0].length(), m = words.length;
        for(int i = 0; i < len; i++) {
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                //进窗口 维护count
                String in = s.substring(right, right + len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                //判断
                if(right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    //维护count
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);
                    //出窗口
                    left += len;
                }
                //更新结果
                if(count == m) {
                    list.add(left);
                }
            }
        }
        return list;
    }

    /**
     * 8.最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        char[] tt = t.toCharArray();
        char[] ss = s.toCharArray();

        int[] hash1 = new int[128];//统计字符串t中字符的频率
        int kinds = 0;//统计字符串t中有多少种字符
        for(char ch : tt) {
            if(hash1[ch]++ == 0) kinds++;
        }

        int minLen = Integer.MAX_VALUE;
        int preIndex = -1;
        int[] hash2 = new int[128];//统计窗口中字符的频率
        for(int left = 0, right = 0, count = 0; right < ss.length; right++) {
            char in = ss[right];
            if(++hash2[in] == hash1[in]) count++;//进窗口 + 维护count
            while(count == kinds) {
                if(right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    preIndex = left;
                }
                char out = ss[left++];
                if(hash2[out]-- == hash1[out]) count--;//出窗口 + 维护count
            }
        }
        if(preIndex < 0 ) return new String();
        return s.substring(preIndex,preIndex + minLen);
    }
    public static void main(String[] args) {
        List<Integer> ret = findAnagrams("cbaebabacd", "abc");
        System.out.println(ret);
    }
}
